﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace WinSort.Ctrl {
    public abstract class BaseSort {
        public int[] list;
        public Action<IEnumerable<int>> action;
        public BaseSort() {

        }
        public BaseSort(int[] list, Action<IEnumerable<int>> action) {
            this.list = list;
            this.action = action;
        }
        public abstract string Name { get;}

        public abstract void Sort();
    }

    public class BubbleSorter : BaseSort {
        public BubbleSorter() {

        }
        public BubbleSorter(int[] list, Action<IEnumerable<int>> action)
            : base(list, action) {
              
        }

        public override void Sort() {
            int i, j, temp;
            bool done = false;
            j = 1;
            while ((j < list.Length) && (!done)) {
                done = true;
                for (i = 0; i < list.Length - j; i++) {
                    if (list[i] > list[i + 1]) {
                        done = false;
                        temp = list[i];
                        list[i] = list[i + 1];
                        list[i + 1] = temp;
                        action(list);
                    }
                }
                j++;
            }
        }

        public override string Name {
            get { return "冒泡排序"; }
        }
    }

    public class SelectionSorter : BaseSort {
        public SelectionSorter() {

        }
        private int min;

        public SelectionSorter(int[] list, Action<IEnumerable<int>> action)
            : base(list, action) {
                
        }

        public override void Sort() {
            for (int i = 0; i < list.Length - 1; i++) {
                min = i;
                for (int j = i + 1; j < list.Length; j++) {
                    if (list[j] < list[min])
                        min = j;
                }
                int t = list[min];
                list[min] = list[i];
                list[i] = t;

                action(list);
            }
        }

        public override string Name {
            get { return "选择排序"; }
        }
    }

    public class ShellSorter : BaseSort {

        public ShellSorter() {

        }
        public ShellSorter(int[] list, Action<IEnumerable<int>> action)
            : base(list, action) {
                
        }


        public override void Sort() {
            int inc;
            for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
            for (; inc > 0; inc /= 3) {
                for (int i = inc + 1; i <= list.Length; i += inc) {
                    int t = list[i - 1];
                    int j = i;
                    while ((j > inc) && (list[j - inc - 1] > t)) {
                        list[j - 1] = list[j - inc - 1];
                        j -= inc;
                    }
                    list[j - 1] = t;

                    action(list);
                }
            }
        }

        public override string Name {
            get { return "希尔排序"; }
        }
    }

    public class InsertionSorter : BaseSort {
        public InsertionSorter() {

        }
        public InsertionSorter(int[] list, Action<IEnumerable<int>> action)
            : base(list, action) {
            
        }

        public override void Sort() {
            for (int i = 1; i < list.Length; i++) {
                int t = list[i];
                int j = i;
                while ((j > 0) && (list[j - 1] > t)) {
                    list[j] = list[j - 1];
                    --j;
                    action(list);
                }
                list[j] = t;
            }
        }

        public override string Name {
            get { return "插入排序"; }
        }
    }


    public class QuickSorter : BaseSort {

        public QuickSorter() {

        }
        public QuickSorter(int[] list, Action<IEnumerable<int>> action)
            : base(list, action) {
               
        }
 
        void OptimizedQuickSort(ref int[] Arr, int Left, int Right) {
            int Pivot;
            Pivot = QuickSort(ref Arr, Left, Right);
            if (Left < Pivot - 1) {
                OptimizedQuickSort(ref Arr, Left, Pivot - 1);
            }
            if (Right > Pivot + 1) {
                OptimizedQuickSort(ref Arr, Pivot + 1, Right);
            }
        }

        int QuickSort(ref int[] Arr, int Left, int Right) {
            int Pivot;
            Pivot = Arr[Left];
            while (Left < Right) {
                while ((Arr[Right] >= Pivot) && (Left < Right)) {
                    Right--;
                }
                if (Left != Right) {
                    Arr[Left] = Arr[Right];
                    Left++;
                }
                while ((Arr[Left] <= Pivot) && (Left < Right)) {
                    Left++;
                }
                if (Left != Right) {
                    Arr[Right] = Arr[Left];
                    Right--;
                }
                action(Arr);
            }
            Arr[Left] = Pivot;
            return Left;
        }  

        public override void Sort() {
            OptimizedQuickSort(ref list, 0, list.Length-1);
        }

        public override string Name {
            get { return "快速排序"; }
        }
    }
}